/*
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <hash_map>
#include <set>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;

void print(int a[9][9]){
	for(int i=0;i<9;i++){
		for(int k=0;k<9;k++)
			cout<<a[i][k]<<" ";
		cout<<endl;
	}
}
void print(vector<vector<char>>& board){
	for(int i=0;i<9;i++){
		for(int k=0;k<9;k++)
			cout<<board[i][k];
		cout<<endl;
	}
}
vector<vector<char>>loadBoard(){
	vector<vector<char>>board;
	char ch;
	vector<char>row;
	FILE* fp=fopen("sudoku.txt" ,"r"); 
	for(int k=0;k<9;k++){
		row.clear();
		for(int i=0;i<9;i++){
			fscanf(fp,"%c",&ch);
			row.push_back(ch);
		}
		fscanf(fp,"%c",&ch);
		board.push_back(row);
	}
	return board;
}
bool isValidSudoku(vector<vector<char>>& board) {
	int row[9][10],column[9][10],block[9][10];
	memset(column,0,90*sizeof(int));
	memset(row,0,90*sizeof(int));
	memset(block,0,90*sizeof(int));
	for(int i=0;i<9;i++){
		for(int k=0;k<9;k++){
			if(board[i][k]!='.'){
				if(row[i][board[i][k]-'0']==1||column[k][board[i][k]-'0']==1||block[i/3*3+k/3][board[i][k]-'0']==1)
					return false;
				else{
					row[i][board[i][k]-'0']=1;column[k][board[i][k]-'0']=1;block[i/3*3+k/3][board[i][k]-'0']=1;
				}
			}
		}
	}
	return true;
}

vector<vector<int>> refreshMap(vector<vector<char>>& board){
	vector<vector<int>>mp;
	vector<int>rmp;
	int row[9][10],column[9][10],block[9][10];
	memset(column,0,90*sizeof(int));
	memset(row,0,90*sizeof(int));
	memset(block,0,90*sizeof(int));
	for(int i=0;i<9;i++){
		for(int k=0;k<9;k++){
			if(board[i][k]!='.'){
				row[i][board[i][k]-'0']=1;column[k][board[i][k]-'0']=1;block[i/3*3+k/3][board[i][k]-'0']=1;
			}
		}
	}
	for(int i=0;i<9;i++){
		for(int k=0;k<9;k++){
			rmp.clear();
			if(board[i][k]=='.'){
				int len=0;
				rmp.push_back(len);
				for(int w=1;w<=9;w++){
					if(row[i][w]==0&&column[k][w]==0&&block[i/3*3+k/3][w]==0){
						rmp.push_back(w);
						len++;
					}
				}
				rmp[0]=len;
			}
			mp.push_back(rmp);
		}
	}
	return mp;
}
bool isvalidMap(vector<vector<char>>& board,vector<vector<int>> cmp){
	for(int i=0;i<9;i++){
		for(int k=0;k<9;k++){
			if(board[i][k]=='.'&&cmp[i*9+k][0]==0){
				return false;
			}
		}
	}
	return true;
}
int xxx=0;
bool solveSudoku2(vector<vector<char>>& board,vector<vector<int>> cmp) {
	for(int i=0;i<9;i++){
		for(int k=0;k<9;k++){
			if(board[i][k]=='.'){
				for(int w=1;w<=cmp[i*9+k][0];w++){
					board[i][k]=cmp[i*9+k][w]+'0';
					vector<vector<int>> tmp=refreshMap(board);
					if(!isvalidMap(board,tmp)){
						continue;
					}
					if(solveSudoku2(board,tmp))
						return true;
				}
				board[i][k]='.';
				return false;
			}
		}
	}
	return true;
}
void solveSudoku(vector<vector<char>>& board) {
	vector<vector<int>> mp=refreshMap(board);
	solveSudoku2(board,mp);
}
int main(){

	int a[]={14,5,67,0,-1,0,-2,2};
	vector<int>v1(a,a+sizeof(a)/sizeof(int));
	vector<int>v2;
	vector<string> result;
	vector<vector<char>>board=loadBoard();
	cout<<isValidSudoku(board)<<endl;
	solveSudoku(board);
	print(board);
	system("pause");
	return 0;
}
*/